package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 647. 回文子串
 * @date 2025/2/14 10:13
 */
public class E647 {

    /**
     * <h3>方法一：中心扩展法</h3>
     *
     * @param s 字符串
     * @return 回文子串个数
     */
    public int countSubstrings1(String s) {
        char[] charArray = s.toCharArray();
        int count = 0;
        // 1. 遍历字符串
        for (int i = 0; i < charArray.length; i++) {
            // 1.1 遍历字符串的每一个字符作为中心向两边扩展
            count += extend(charArray, i, true);
            // 1.2 遍历字符串的每一个字符和后一个字符作为中心向两边扩展
            count += extend(charArray, i, false);
        }
        return count;
    }

    /**
     * 扩展中心
     *
     * @param charArray 字符数组
     * @param index     中心索引
     * @param oddExtend 是否为奇数扩展
     * @return 回文子串个数
     */
    private int extend(char[] charArray, int index, boolean oddExtend) {
        // 如果为偶数扩展，且后一个字符超出数组范围或者当前字符和下一个字符不相等，则直接返回0
        if (!oddExtend && (index == charArray.length - 1 || charArray[index] != charArray[index + 1])) return 0;
        // 准备left, right指针、count
        int left = index - 1, right = oddExtend ? index + 1 : index + 1 + 1;
        int count = 1;
        // 当left和right指针在范围内，并且left和right指向的字符相等时，继续向两边扩展
        while (left >= 0 && right < charArray.length && charArray[left] == charArray[right]) {
            count++;
            left--;
            right++;
        }
        return count;
    }

    /**
     * <h3>方法二：动态规划，时间复杂度接近O(n^3)</h3>
     *
     * @param s 字符串
     * @return 回文子串个数
     */
    public int countSubstrings2(String s) {
        char[] charArray = s.toCharArray();
        int[] dp = new int[charArray.length];
        dp[0] = 1;
        for (int i = 1; i < charArray.length; i++) {
            dp[i] += dp[i - 1];
            for (int j = 0; j <= i; j++){
                int left = j, right = i;
                while (left < right && charArray[left] == charArray[right]){
                    left++;
                    right--;
                }
                if (left >= right) dp[i]++;
            }
        }
        return dp[charArray.length - 1];
    }

    /**
     * <h3>方法三：动态规划，对方法二的优化，时间复杂度接近O(n^2)</h3>
     *
     * @param s 字符串
     * @return 回文子串个数
     */
    public int countSubstrings3(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n]; // dp[i][j] 表示 s[i...j] 是否是回文子串
        int count = 0; // 记录回文子串的数量
        // 从字符串末尾开始遍历
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                // 如果当前字符相等
                if (s.charAt(i) == s.charAt(j)) {
                    // 情况1：单个字符（i == j）
                    // 情况2：两个字符（j - i == 1）
                    // 情况3：长度大于2，且内部子串是回文（dp[i+1][j-1]）
                    if (j - i <= 1 || dp[i + 1][j - 1]) {
                        dp[i][j] = true; // 标记为回文子串
                        count++; // 增加计数
                    }
                }
            }
        }
        return count;
    }
}
